package classes;

import java.util.ArrayList;
import java.util.List;

public class ExtrapolateND {
	
	public static float linearEx(float K[], float matrix[][]) throws Exception {
		return linearEx(0,K,matrix);
	}
	
	public static float	linearEx(int depth, float K[], float matrix[][]) throws Exception {
		//
		// This method is very complicated. But here goes.
		// 
		//
		int		M0[];
		int		M1[];
		float	matrix0[][];
		float	matrix1[][];
		int		B[];
		float	X[], Y[];
		float	x0, x1;
		float	y0, y1;
		float	z;
		float	known;
		
		known = K[depth];
		
		if (depth<K.length-1) {
			//
			// We are on our last dimension of K
			// Retrieve the two closest x values to form the line from this dimension
			//
			X = getCol(depth,matrix);
			
			if (X.length>1) {
				//
				// There is two data points to linear extrapolation from. Continue
				//
				
				B = lineClosest(X,known);
				
				// Remember the two values
				x0 = X[B[0]];
				x1 = X[B[1]];
				
				// Find the matching rows for x0 and linear extrapolate that matrix
				M0 = selectMatchingRows(depth, x0, matrix);
				matrix0 = selectRows(M0, matrix);
				y0 = linearEx(depth+1, K, matrix0);
		
				// Check if slope is infinite then we return whatever y0 is
				if (x0==x1) {
					return y0;
				}
				
				// Find the matching rows for x1 and linear extrapolate that matrix
				M1 = selectMatchingRows(depth, x1, matrix);
				matrix1 = selectRows(M1, matrix);
				y1 = linearEx(depth+1, K, matrix1);
				
				// Take the two results and linear extrapolate a new result
				System.out.printf("*** z at depth %d/%d\n",depth,K.length);
				z = linear(x0, y0, x1-x0, y1-y0, known);
			} else {
				z = 0f;
			}
			
			// Return the extrapolated result
			return z;
		} else {
			//
			// Retrieve the two closest x values to form the line from this dimension
			//
			X = getCol(depth,matrix);
			Y = getCol(depth+1, matrix);

			if (X.length>1) { 
				B = lineClosest(X,K[depth]);
				// Remember the two values
				x0 = X[B[0]];
				x1 = X[B[1]];
				
				// Find the matching y0 values for x0 and x1
				y0 = Y[B[0]];
				
				// Check if slope is infinite then we return whatever y0 is
				if (x0==x1) { 
					throw new Exception("Error in linearEx() at depth = " + depth + " : dx=0 Infinite slope for the line!");
				}
				
				// Find the matching rows for x1 and linear extrapolate that matrix
				y1 = Y[B[1]];

				// Take the two results and linear extrapolate a new result
				System.out.printf("*** z at depth %d/%d\n",depth,K.length-1);
				z = linear(x0, y0, x1-x0, y1-y0, known);
				
			} else if (X.length==1 && K[depth]== X[0]) {
				return Y[0];
			} else {
				throw new Exception("Error in linearEx() at depth = " + depth + " : Not enough data for linear extrapolation");
			}
				
			// Return the extrapolated result
			return z;
			
		}
	}

	// ***** COPIED FROM CLASS Algebra
	public static int numRows(float matrix[][]) {
		return matrix.length;
	}
	public static int numCols(float matrix[][]) {
		if (numRows(matrix)>0) {
			return matrix[0].length;
		} else {
			return 0;
		}
	}


	public static float[] getCol(int col, float m[][]) {
		float	v[] = new float[numRows(m)];
		int		i;
		for(i=0; i<numRows(m); i++) {
			v[i] = m[i][col];
		}
		return v;
	}
	
	public static float	linear(float x, float y, float dx, float dy, float Tx) {
		if (dx==0) {
			return Float.POSITIVE_INFINITY;
		} else {
			float	m = dy/dx;
			float	b = y-m*x;
			float	Ty = m*Tx+b;
//			System.out.printf("**********************************************************\n");
//			System.out.printf("     dy                          %5.2f                    \n", dy);    
//			System.out.printf("Y = ---- X + B    ==     %5.2f = ------ ( %5.2f ) + %5.2f \n", Ty,Tx,b);  
//			System.out.printf("     dx                          %5.2f                    \n", dx);
//			System.out.printf("**********************************************************\n");
			return	Ty;
		}
	}
	
	public static int[]	lineClosest(float data[], float target) {
		int	B[] = twoClosestButDifferent(data, target);
		if (data[B[0]] > data[B[1]]) {
			return new int[] { B[1], B[0] };
		} else {
			return B;
		}
	}
	
	public static int[] twoClosestButDifferent(float data[], float target) {
		//
		// Returns indicies of the two closest points in the data set
		// This will NOT return them sorted by distance from the point
		//
		int		m0 = -1, m1 = -1;
		float	d0 = Float.POSITIVE_INFINITY, d1 = Float.POSITIVE_INFINITY, di = Float.POSITIVE_INFINITY;
		float	v0 = Float.POSITIVE_INFINITY, vi = Float.POSITIVE_INFINITY;
		int		i;
		int		found = 0;
		
		for(i=0; i<data.length; i++) {
			
			di = Math.abs(data[i]-target);
			vi = data[i];
			
			if (found==0) {
				m0 = i;
				d0 = di;
				found = 1;
			} else {
				if (vi != v0 && (found==1 || di <= d0)) {
					m1 = m0;
					d1 = d0;
					m0 = i;
					d0 = di;
					v0 = vi;
					found = 2;
				} else if (found==1 || di < d1) {
					m1 = i;
					d1 = di;
					found = 2;
				}
			}
		}
		return new int[] { m0, m1 };
		
	}
	
	public static int[]	selectMatchingRows(int col, float value, float M[][]) {
		ArrayList<Integer> L = new ArrayList<Integer>();
		int	i;
		for(i=0; i<numRows(M); i++) {
			if (M[i][col]==value) {
				L.add(new Integer(i));
			}
		}
		return toArray(L);
	}
	
	public static float[][]	selectRows(int rows[], float M[][]) {
		float	N[][] = new float[rows.length][numCols(M)];
		int		i;
		for(i=0; i<rows.length; i++) {
			N[i] = getRow(rows[i],M);
		}
		return N;
	}
	
	public static float[] getRow(int row, float m[][]) {
		float	v[] = new float[numCols(m)];
		int		i;
		for(i=0; i<numCols(m); i++) {
			v[i] = m[row][i];
		}
		return v;
	}
	
	private static int[] toArray(List<Integer> L) {
		int r[] = new int[L.size()];
		int	i;
		for(i=0; i<L.size(); i++) {
			r[i] = L.get(i).intValue();
		}
		return r;
	}
	
}



